package middle;

import entity.Node;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.concurrent.LinkedBlockingQueue;

/**
 * 116. 填充每个节点的下一个右侧节点指针
 */
public class Connect {

    public static Node stringToTreeNode(String input) {
        input = input.trim();
        input = input.substring(1, input.length() - 1);
        if (input.length() == 0) {
            return null;
        }

        String[] parts = input.split(",");
        String item = parts[0];
        Node root = new Node(Integer.parseInt(item));
        Queue<Node> nodeQueue = new LinkedList<>();
        nodeQueue.add(root);

        int index = 1;
        while (!nodeQueue.isEmpty()) {
            Node node = nodeQueue.remove();

            if (index == parts.length) {
                break;
            }

            item = parts[index++];
            item = item.trim();
            if (!item.equals("null")) {
                int leftNumber = Integer.parseInt(item);
                node.left = new Node(leftNumber);
                nodeQueue.add(node.left);
            }

            if (index == parts.length) {
                break;
            }

            item = parts[index++];
            item = item.trim();
            if (!item.equals("null")) {
                int rightNumber = Integer.parseInt(item);
                node.right = new Node(rightNumber);
                nodeQueue.add(node.right);
            }
        }
        return root;
    }

    public static String treeNodeToString(Node root) {
        if (root == null) {
            return "[]";
        }

        String output = "";
        Queue<Node> nodeQueue = new LinkedList<>();
        nodeQueue.add(root);
        while (!nodeQueue.isEmpty()) {
            Node node = nodeQueue.remove();

            if (node == null) {
                output += "null, ";
                continue;
            }

            output += String.valueOf(node.val) + ", ";
            nodeQueue.add(node.left);
            nodeQueue.add(node.right);
        }
        return "[" + output.substring(0, output.length() - 2) + "]";
    }

    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        String line;
        while ((line = in.readLine()) != null) {
            Node root = stringToTreeNode(line);

            Node ret = new Solution().connect(root);

            String out = treeNodeToString(ret);

            System.out.print(out);
        }
    }

    static class Solution {
        public Node connect(Node root) {
            if (root==null){
                return null;
            }
            dfs(root,null);
            return root;
        }

        void dfs(Node node,Node right){
            if (node.left!=null){
                if (node.right!=null){
                    node.left.next = node.right;
                }
                dfs(node.left,node.right);
            }

            if (node.right!=null){
                if (right!=null&&right.left!=null){
                    node.right.next = right.left;
                }
                dfs(node.right,right==null?null:right.left);
            }

        }


    }


//    static class Solution {
//        public Node connect(Node root) {
//            if (root==null){
//                return root;
//            }
//            bfs(root);
//            return root;
//        }
//
//        void bfs(Node root) {
//            Queue<Node> queue = new LinkedBlockingQueue<>();
//            List<Node> nextList = new ArrayList<>();
//            queue.offer(root);
//            while (!queue.isEmpty()) {
//                Node item = queue.poll();
//                Node next = queue.peek();
//                item.next = next;
//                if (item.left != null) {
//                    nextList.add(item.left);
//                }
//                if (item.right != null) {
//                    nextList.add(item.right);
//                }
//                if (next==null){
//                    queue.addAll(nextList);
//                    nextList.clear();
//                }
//            }
//        }
//    }

}
